Floorplanning, also called chip planning, is the process of determining the most efficient arrangement of functional devices upon an integrated circuit chip. The goals of floorplanning are to: obtain a reliable estimation of an integrated circuit chip's routability; obtain accurate delay estimations prior to layout; analyze and control the delays of networks; analyze and control the skew of networks; facilitate layout; and, improve system-level performance. The end result is a floorplan which is a physical layout showing placement relationships between major top level logic blocks.
The objective of floorplanning is to organize all logic within well defined, easily identifiable, and understandable elements of the hierarchy. A hierarchy contains an all-inclusive top-level function composed of one or more lower-level functions.
A "function" consists of a logic or memory element. A function may be an element or a combination of a number of elements. A function or functional block is a module (or part) in a design's hierarchy that contains connected components. More specifically, functions or functional blocks contain connected components such as megacells, macrocells, macro-functions, lower-level blocks, and their inputs and outputs. A function may be as simple as an inverter or a flip-flop, consisting of one or only a few transistors, or as complex as a shift register, an ALU or even an entire microprocessor, consisting of hundreds of thousands of transistors.
From a mathematical point of view, both formulating and solving the floorplanning problem are quite difficult. A precise mathematical solution essentially cannot be obtained. Heuristic algorithms are therefore employed to approximate the optimum solution to the floorplanning problem.
Moreover, due to the increasing complexity of chip designs, necessitating more and more logic and/or memory elements per unit area, the complexity of the floorplanning problem has increased dramatically. It is, therefore, extremely advantageous to automate this process in some fashion.
Prior to the floorplanning process itself, which involves the placement of functional blocks on a integrated circuit chip, the integrated circuit chip's logic must be designed. Logic designers generally employ hierarchical design techniques to determine the appropriate selection and interconnection of logic and/or memory functions which will enable the integrated circuit chip to perform the desired function. These techniques involve describing the integrated circuit chip's functionality at various "levels of abstraction," ranging from the most general function performed by the integrated circuit chip to the precise functions performed by each logic and/or memory element on the integrated circuit chip.
Thus, a logic designer's hierarchy consists of N levels of functions, where N is an integer (N.gtoreq.1) representing the number of hierarchical levels of functionality in the integrated circuit chip, the first level being the integrated circuit chip itself, and where n is an integer (1.ltoreq.n.ltoreq.N) representing the level of any particular function in the hierarchy.
A "parent" function is the (n).sup.th level of the hierarchy is defined as a plurality of (n+1).sup.st level "children" functions, each of which is a "child" function. For example, a microprocessor at the (n).sup.th level might be defined as the parent of the following (n+1).sup.st level children: an ALU, a series of registers, a bus and various other functions (each of which may or many not have a plurality of (n+2).sup.nd level children, and so on).
Note that lower levels of the hierarchy are commonly denoted by successively higher numbers. Thus, while level 1 refers to the top (integrated circuit chip) level of the hierarchy, levels 2, 3 and 4 constitute successively "lower" levels of the hierarchy.
Each child function which is not also a parent function (i.e., which has no children) is referred to as a "terminal" (or "leaf") function. Accordingly, a terminal function is a function at the lowest level of the design's hierarchy since it does not contain any lower-level blocks. Each terminal function is connected to at least one other terminal function, such connection being commonly referred to as a "net." A series of nets, each of which defines a plurality of interconnected functions, is commonly referred to as a "net list."
Major concerns of a logic design include routability and feasibility. Feasibility is a percent representing the probability of layout of a particular design in a specified integrated circuit chip area. Routability is a measure of how easy it will be to interconnect all of the elements in a given design.
Feasibility is calculated by first randomly placing the functions in the specified integrated circuit chip area, and then determining how much routing space is actually required. The feasibility percent equals the availability space for routing (specified integrated circuit chip area less the sum of the areas of all functions) divided by the routing space actually required. This percent is, of course, limited to 100%. The placement of functions can be undertaken using random, pseudo-random, and heuristic approaches.
Previous floorplanning techniques determined routability by hierarchical estimation of the unknown function area as well as the optimization of hierarchical interconnections of functions. Estimating the mount of routing space requires a means of estimating a function's area that it encompasses. Estimation is necessary at the initial stages of floorplanning since the precise area of a function may be unknown because certain functions have not been laid out.
Former inventions, such as U.S. Pat. No. 4,918,614, attempted to solve this problem by estimating the area of terminal functions whose elements have not been laid out and their respective parent functions. Requisite routing space can also be estimated by algorithms such as one that takes into account the shape or size and relative location of a particular module to the other modules, required interconnections to Inpututput ("I/O") pads, and heuristically estimating the connections routing and end-points, among other methods.
Current floorplanning methods use design information from the logic systems and from a bonding diagram program to place functional blocks on a integrated circuit chip automatically. Block placement allows for accurate delay estimation calculations. Once the blocks are placed, analysis of the connections between blocks, and changes in block sizes, shapes, positions, or connections to improve the pre-layout estimated delays of user-defined critical nets can take place.
Current floorplanning processes also provide the user with both graphic and alphanumeric information. Blocks are displayed in the sizes and shapes that they occupy in the integrated circuit chip. Lines of various widths represent relative numbers of connections between blocks. The width of the line connecting two blocks reflects the number of wires connecting cells between them, relative to the number of wires connecting cells between other blocks.
Previous floorplanning techniques roughly fall into two basic categories: (1) "flat" floorplanners, which attempt to minimize space at only one level (the "level" which is created when the hierarchy is flattened by omitting all but the terminal functions, by placing all but the terminal functions), by placing only terminal functions; and (2) "top-automated" floorplanners, which automate the floorplanning process at only the top level, by placing only two dimensional (2D) level functions.
Significant disadvantages of former methods of floorplanning include: requiring that connection computations be done first, which may not be necessary when a particular location candidate set is being analyzed; providing insufficient efficiency when considering multiple integrated circuit chips; and, no means of optimizing across multiple integrated circuit chips.
Prior floorplanning techniques have been limited to concentrating upon one integrated circuit chip of an integrated circuit. This entailed inputting information about the structure of the integrated circuit chip being analyzed as well as information about the connections which one integrated circuit chip would have with respect to all other integrated circuit chips. Subsequent logic changes would then require that simulation sequences be undertaken to obtain results. However, no modifications could be made to any other integrated circuit chip. Modifications to any other integrated circuit chip would require the user to enter updated structure and connection information of the second integrated circuit chip and then determine results.
This tedious process of updating and analyzing each integrated circuit chip individually was necessary until a satisfactory design was achieved. Thus, the efficiency of prior floorplanning techniques for integrated circuits with multiple integrated circuit chips was laborious, time consuming and inefficient.
Prior floorplanning techniques became most inefficient when a recombination of functional blocks was sought between two integrated circuit chips. For example, in a given integrated circuit chip set, a particular circuit could conceivably be located on any one of the integrated circuit chips. However, each integrated circuit chip had to be laid out separately. The available floorplanning techniques did not allow for the simultaneous optimization of multiple integrated circuit chips to determine the best location for such a circuit. When one functional block was desired to be moved from one integrated circuit and added to a second integrated circuit, it required that the first integrated circuit chip and the second integrated circuit chip be separately reanalyzed after the entering of revised inputs and a revised circuit configuration for each of the integrated circuit chips.
Although prior efforts may have provided a hierarchical floorplanning system that approximated a globally optimum solution to the floorplanning problem with regard to a particular integrated circuit, no prior an system has been able to provide a floorplanning system that is able to analyze and adjust a logic design which requires movement of functional blocks between integrated circuit chips. Therefore, prior floorplanning techniques were unable to achieve optimization across multiple integrated circuit chips.